class Solution(object):
    def confusingNumberII(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        num = n
        while num // 10 > 0:
            count += 1
            num = num // 10
        count += 1
        wait = [0, 1, 6, 8, 9]
        d = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}

        def judge(value):
            if value > n:
                return False
            else:
                s = str(value)
                t = ''
                for i in range(len(s)):
                    t += d[s[-i - 1]]
                return t != s

        def search(i):
            out = set()
            if i < count:
                if i == 1:
                    for j in wait:
                        out.add(j)
                else:
                    base = search(i - 1)
                    for item in base:
                        for j in wait:
                            out.add(item + j * 10 ** (i - 1))
            else:
                base = search(i - 1)
                for j in wait:
                    if j <= num:
                        for item in base:
                            value = item + j * 10 ** (i - 1)
                            if judge(value):
                                out.add(value)
            return out

        return len(search(count))


data = Solution()
n = 10 ** 9
print(data.confusingNumberII(n))
